package sort;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/4/1 17:01
 */
public class 计数排序 {
    /*
     计数 排序, 就很简单了!
     思路 和实现 很简单, 时间复杂度 O(N)
     空间复杂度 O( max (nums[i]) )
     但是 对 数据的格式 是有要求的,稳定的

     ==
     如果 数据 有负数的 话 ,还需要 一些 麻烦的转换, 还是 挺麻烦的
     ,所以说这种排序的限制 ,很大!
     */


    public void countSort(int nums[]){
        /*
         如果 这里 使用 TreeMap 的话, 这里的时间复杂度就不是 O(N)
         TreeMap 本身的  时间复杂度 就是 O(N * lgN)
         */
        int len = nums.length;
        int max = 0;
        for(int num : nums){
            max = Math.max(num,max);
        }
        // 这个就是 额外使用的 空间
        int count[] = new int[max + 1];

        for(int num : nums){
            count[num]++;
        }
        int index = 0;
        for(int i = 0;i <= max;i++){
            if(count[i]!= 0){
                int cnt = count[i];
                while(cnt-- > 0){
                    nums[index++] = i;
                }
            }

        }
    }

    @Test
    public void test(){
//        int arr[] = {4, 5, 8, 7, 7, 3, 2, 6, 8, 7};
//        countSort(arr);
//        System.out.println(Arrays.toString(arr));
        testRight();
    }
    /**
     * 首先生成 随机数组的函数！
     *
     * @param arraySize 数组的大小（根据 题目的 不同， 也可能是 一个数组的  最大长度， 随机生成 数组的 长度 在 1 ~  arraySize 之间）
     * @param max       数组中元素的最大值
     * @param min       一个指标， 如果 min = 0， 代表 数组中的元素，>=0 ，min = 1， 代表 全是正数  min = -1 ，可正 ke 负 ， 可为 0
     * @param fix       如果 fix = true 代表， 数组的长度 固定， 反之， 数组的长度 不固定
     * @return 一个 生成的随机的数组(长度可以随机， 也可以 固定， 看具体题目的要求)
     */
    public int[] ramdomArray(int arraySize, int max, int min, boolean fix) {
        int ramdomArraySize = fix ? arraySize : (int) (Math.random() * (arraySize + 1)); // 数组的长度 , 由fix 来控制 是否随机
        int arr[] = new int[ramdomArraySize];
        if (min == 0) {
            for (int i = 0; i < ramdomArraySize; i++) {
                arr[i] = (int) (Math.random() * (max + 1)); // arr[i] = [0 , max]
            }
        } else if (min == 1) {
            for (int i = 0; i < ramdomArraySize; i++) {
                arr[i] = (int) (Math.random() * (max)) + 1;//  arr[i] =  [1 , max + 1)
            }
        } else {
            for (int i = 0; i < ramdomArraySize; i++) {
                arr[i] = (int) (Math.random() * (max + 1) - Math.random() * (max + 1)); // 可正 可 负 可为 0
            }
        }
        return arr;
    }


    public void testRight() {
        int testTimes = 10000; // 自己写！
        int arraySize = 100;
        int max = 50;
        int min = 0;
        boolean fix = false;
        boolean isSuccess = true;
        for(int i = 0;i <  testTimes;i++){
            int[] ints = ramdomArray(arraySize, max, min, fix);
            int arr1[] = Arrays.copyOf(ints, ints.length);
            int arr2[] = Arrays.copyOf(ints, ints.length);
            // 你的方法
            countSort(arr1);
            Arrays.sort(arr2);
            if(!Arrays.equals(arr1,arr2)){
                 /*
                  说明 有问题， 可以打印下，数组，看下是什么 问题！
                  */
                isSuccess = false;
                System.out.println(Arrays.toString(ints));
            }
        }
        System.out.println(isSuccess ? "success" : "fuck!");
    }
    public void testRight1() {
        int testTimes = 100; // 自己写！
        int arraySize = 10;
        int max = 50;
        int min = -1;
        boolean fix = false;
        boolean isSuccess = true;
        for(int i = 0;i <  testTimes;i++){
            int[] ints = ramdomArray(arraySize, max, min, fix);
            System.out.println(Arrays.toString(ints));
        }
    }

    @Test
    public void test1(){
        testRight1();
    }
}
